package SubString;


import java.util.HashMap;
import java.util.Map;

/**
 * 76.最小覆盖字串
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 * 注意：
 * ● 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
 * ● 如果 s 中存在这样的子串，我们保证它是唯一的答案。
 */
public class minWindow {

    /**
     * hot100一刷
     * hot100二刷
     */
    class Solution {
        public String minWindow(String S, String t) {
            char[] s = S.toCharArray();
            int m = s.length;
            int ansLeft = -1;
            int ansRight = m;
            int[] cntS = new int[128]; // s 子串字母的出现次数
            int[] cntT = new int[128]; // t 中字母的出现次数
            for (char c : t.toCharArray()) {
                cntT[c]++;
            }

            int left = 0;
            for (int right = 0; right < m; right++) { // 移动子串右端点
                cntS[s[right]]++; // 右端点字母移入子串
                while (isCovered(cntS, cntT)) { // 涵盖
                    if (right - left < ansRight - ansLeft) { // 找到更短的子串
                        ansLeft = left; // 记录此时的左右端点
                        ansRight = right;
                    }
                    cntS[s[left]]--; // 左端点字母移出子串
                    left++;
                }
            }
            return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
        }

        private boolean isCovered(int[] cntS, int[] cntT) {
            for (int i = 'A'; i <= 'Z'; i++) {
                if (cntS[i] < cntT[i]) {
                    return false;
                }
            }
            for (int i = 'a'; i <= 'z'; i++) {
                if (cntS[i] < cntT[i]) {
                    return false;
                }
            }
            return true;
        }
    }





}
